package com.tys.algorithm.bak.code1;

import java.util.Arrays;

//基数排序：使用count和count累加和实现桶效果
//非负并且十进制表示
public class Code37_RadixSort {
    //arr数组中不能出现 负数
    public static void radixSort(int[] arr) {
        //边界判断
        if (arr == null || arr.length < 2) {
            return;
        }
        //排序
        radixSort(arr, 0, arr.length - 1, maxbits(arr));
    }

    //获取数据组中最大值的位数
    //134是3位，88234是5位
    public static int maxbits(int[] arr) {
        int max = Integer.MIN_VALUE; //最大值，设置为整数最小值
        //遍历数组得到最大值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        //计算最大值是几位
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res; //返回位数
    }


    /**
     * arr[L...R]排序
     *
     * @param arr   数组
     * @param L     左边界
     * @param R     右边界
     * @param digit 指定几位数
     */
    public static void radixSort(int[] arr, int L, int R, int digit) {
        //指定基数：0-9
        final int radix = 10;
        int i = 0, j = 0;
        //辅助数组
        int[] help = new int[R - L + 1];
        //进桶出桶几次，几位就几次
        //从个位，十位、百位依次遍历
        //d=1个位，d=2十位，d=3百位。。。
        for (int d = 1; d <= digit; d++) {
            //计数数组，记录数字出现几次
            int[] count = new int[radix];
            //遍历arr数组找到指定位d位的数，count对应计数为加1
            //count[0] 0出现了几次
            //count[1] 1出现了几次
            //count[2] 2出现了几次
            for (i = L; i <= R; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            //累加和
            //count[0] <=0的数有几个
            //count[1] <=1的数有几个
            //count[2] <=2的数有几个
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            //从右向左遍历：从右向左填
            for (i = R; i >= L; i--) {
                //j 是arr[i]指定d位的数字
                //arr[i]=123, d=1, j=3, j是123个位数的3
                j = getDigit(arr[i], d);
                //count[j] 有几个数 <=j
                //count[j]-1 表示 arr[i] 放在hep数组的索引位置
                help[count[j] - 1] = arr[i];
                count[j]--; //<=j 的计数减1
            }

            //拷贝help数组到arr
            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = help[j];
            }
        }
    }

    //得到整数x指定d位的数字
    public static int getDigit(int x, int d) {
        // d=1是个位：(x/(10^0))%10
        // d=2是十位: (x/(10^1))%10
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }

    //使用系统比较方法
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    //生成随机数组
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    //拷贝数组
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    //对比两个数组是否相等
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    //打印数组
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100000;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            radixSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

//        int[] arr = generateRandomArray(maxSize, maxValue);
//        printArray(arr);
//        radixSort(arr);
//        printArray(arr);
    }
}
